export interface Goods {
    weight: number;
    price: number;
}
export default function backpack (packWeight: number, goods: Goods[]) {
    const res: number[][] = new Array(goods.length + 1).fill(0)
        .map(() => new Array(packWeight + 1).fill(0));

    for (let i = 1; i <= goods.length; i++) {
        const { weight: goodsWeight, price } = goods[i - 1];
        for (let j = 1; j <= packWeight; j++) {
            // 当背包重量大于货物重量，将货物放进背包占据货物的重量
            // 并比较装满当前货物之后，剩余背包重量可以装货物价值与上一个货物的价值
            if (j >= goodsWeight) {
                res[i][j] = Math.max(price + res[i - 1][j - goodsWeight], res[i - 1][j]);
            }
            else {
                res[i][j] = res[i-1][j];
            }
        }
    }
    return res;
}